package com.hle.sort.cmp;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import com.hle.sort.Sort;
import com.hle.tools.Integers;

public class ShellSort<T extends Comparable<T>> extends Sort<T> {

	@Override
	protected void sort() {
		for (Integer step : shellStepSe()) {
			sort(step);
		}
	}

	private void sort(Integer step) {
		for (int col = 0; col < step; col++) {
			for (int begin = col + step; begin < array.length; begin += step) {
				int curBegin = begin;
				while (curBegin > col && cmp(curBegin, curBegin - 1) < 0) {
					swap(curBegin, curBegin - step);
					curBegin -= step;
				}
			}
		}
	}

	private List<Integer> shellStepSe() {
		List<Integer> list = new ArrayList<>();
		int step = array.length;
		while ((step >>= 1) > 0) {
			list.add(step);
		}
		return list;
	}

}
